package q986_intervalIntersection;

import java.util.ArrayList;
import java.util.List;

public class Solution_1 {
    /*
    标准但繁琐的解法
    分别考虑两个区间之间的关系
    根据不同的关系确定加入res的区间和区间的迭代
     */
    public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
        List<int[]> res = new ArrayList<int[]>();
        if (firstList.length == 0 || secondList.length == 0) {
            return new int[0][];
        }
        int i1 = 0, i2 = 0;
        while (i1 < firstList.length && i2 < secondList.length) {
            int l1 = firstList[i1][0], r1 = firstList[i1][1], l2 = secondList[i2][0], r2 = secondList[i2][1];
            // 区间不相交
            if (r1 < l2) {
                i1++;
                continue;
            }
            if (r2 < l1) {
                i2++;
                continue;
            }

            // 两个区间相交
            if (r1 >= l2 && r1 < r2 && l1 < l2) {
                res.add(new int[]{l2, r1});
                i1++;
                continue;
            }
            if (r2 >= l1 && r2 < r1 && l2 < l1) {
                res.add(new int[]{l1, r2});
                i2++;
                continue;
            }

            // 区间之间包含
            if (r1 >= r2 && l1 <= l2) {
                res.add(new int[] {l2, r2});
                i2++;
                continue;
            }
            if (r2 >= r1 && l2 <= l1) {
                res.add(new int[] {l1, r1});
                i1++;
            }

        }
        int[][] inter = new int[res.size()][];
        for (int i = 0; i < res.size(); i++) {
            inter[i] = res.get(i);
        }
        return inter;
    }
}
